//
// Created by Administrator on 2021/11/16.
// May Saint Diana bless you!
//
#include <iostream>
#include <vector>
#include <unordered_map>
#include <queue>

using namespace std;

class Solution {
public:
    int minSetSize(vector<int> &arr) {
        unordered_map<int, int> counter;// 统计每个数字的个数
        for (const int &x:arr) {
            ++counter[x];
        }
        priority_queue<int, vector<int>, less<>> pq;
        for (const auto &x:counter) {
            pq.push(x.second);
        }
        int ans = 0;
        int total = 0;
        while (total < arr.size() / 2) {
            total += pq.top();
            pq.pop();
            ++ans;
        }
        return ans;
    }
};

int main() {
    vector<int> arr{3, 3, 3, 3, 5, 5, 5, 2, 2, 7};
    Solution solution;
    cout << solution.minSetSize(arr) << endl;
    return 0;
}


